<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      function getLongest(list = []) {
        if (list.length === 0) {
          return 0
        }
        if (list.length === 1) {
          return list[0]
        }
        // 代表当前项的最优解
        const dp = [list[0], Math.max(list[0], list[1])]
        for (let i = 2; i < list.length; i++) {
          // 当前预约两个有选择，可以接或不接
          // 如果接，就是当前项加上两项前的最优解，不接就是上一项的最优解
          dp[i] = Math.max(list[i] + dp[i - 2], dp[i - 1])
        }
        return dp
      }
      console.log(getLongest([2, 1, 4, 5, 3, 1, 1, 3]))

      // 有n节楼梯，一次只能上一节或者两节，总共有多少种上法
      function climb(n) {
        const dp = [0, 1, 2]
        for (let i = 3; i <= n; i++) {
          dp[i] = dp[i - 1] + dp[i - 2]
        }
        console.log(dp);
      }
      climb(20)
    </script>
  </body>
</html>
